#include<iostream>
#include<vector>
using namespace std;

// 数组长度、和
int n=4, t=8;

// 初始化数组
vector<int> a={3, 1, 5, 2};

// 累计解个数
int cnt = 0;

// 输出一个解
void disp(vector<int> &x)
{
	printf("  第%d个解  ",++cnt);
	printf("选取的数为");
	for (int i=0;i<n;i++)
		if (x[i]==1)
			printf("%d ",a[i]);
	printf("\n");
}

// 累计搜索结点个数
int sum = 0;

// 递归算法
void dfs(int cs, int rs, vector<int> &x, int i)
{
	sum++;
	
	// cs为考虑第i个整数时选取的整数和，rs为剩余整数和
	printf("[%d,%d]\n", cs, rs);
	
	// 找到一个叶子结点
	if (i >= n)
	{
		// 找到一个满足条件的解,输出
		if (cs == t)	
			disp(x);
	}
	
	// 没有到达叶子结点
	else
	{
		// 求剩余的整数和
		rs-=a[i];
		
		// 左孩子结点剪支
		if (cs+a[i] <= t)
		{
			// 选取整数a[i]
			x[i] = 1;
			dfs(cs+a[i], rs, x, i+1);
		}
		else 
			printf("左剪支[%d,%d]\n",cs+a[i],rs);
		
		// 右孩子结点剪支
		if (cs+rs >= t)
		{
			// 不选取整数a[i]
			x[i] = 0;
			dfs(cs, rs, x, i+1);
		}
		else
			printf("右剪支[%d,%d]\n",cs,rs);
		
		// 恢复剩余整数和
		rs+=a[i];
	}
}

// 求解子集和问题
void subs3()
{
	// 解向量
	vector<int> x(n);
	
	// 求rs，表示所有整数和
	int rs = 0;
	for (int j=0; j<n; j++)
		rs+=a[j];
	
	// i从0开始
	dfs(0, rs, x, 0);
}

int main()
{
	printf("子集和问题解\n"); 
	subs3();
	printf("sum=%d\n",sum);
	return 0;
}
